August Antonius Neidhardt ra đời vào tháng 10 năm 1760 tại Schildau, gần Torgau, trong một gia đình quý tộc sa sút.[2] Ông là con trai của viên trung tá pháo binh Sachsen August Wilhelm Neidhardt với bà Maria Eva Neidhardt, nhũ danh Müller, con gái viên thượng tá Müller của quân đội Thân vương Tổng giám mục Würzburg. Về sau này, ông đặt thêm tên Gneisenau, theo tên của một điền trang đã mất của gia đình ông ở Áo, vào tên gọi của mình. Trong thời điểm năm 1777, ông chỉ được đề cập trong danh sách sinh viên của Đại học Erfurt với cái tên "August Antonius Neidhardt", trái lại, vào năm 1783, biên chế của quân đội Ansbach-Bayreuth ghi tên ông là "Neidhardt von Gneisenau" và ông tiếp tục giữ cái tên này sau khi nhập ngũ quân đội Phổ.

Khi Gneisenau sinh ra, cha ông đang tham gia cuộc Chiến tranh Bảy năm (1756 – 1763) chống lại vua Phổ là Friedrich Đại đế. Một tuần sau khi ông sinh ra, sự thất trận của quân đội Đế quốc La Mã Thần thánh trong trận Torgau vào ngày 3 tháng 10 năm 1760 đã buộc mẹ của Neidhardt phải bỏ chạy cùng với con mình. Chỉ vài tuần sau, mẹ ông qua đời do kiệt sức trong cuộc di tản và do hoảng hốt vì đánh rơi Neidhart khỏi chiếc xe ngựa của mình. Do người cha bận xông pha trận mạc, đứa bé Neidhart được giao cho những người xa lạ nuôi dưỡng. Đứa trẻ bị bỏ bê một cách thậm tệ. Sau khi biết được hoàn cảnh bất hạnh của cậu bé, ông ngoại của Neidhart là Müller, khi ấy đang sống ở Würzburg, đã nhận trách nhiệm chăm sóc cháu mình. Tại Würzburg, Neidhardt được các giáo sĩ Dòng Tên dạy dỗ, chi đến năm 13 tuổi thì ông về với cha tại Erfurt. Vào năm 1777, ông nhập học Trường Đại học Erfurt, nhưng chỉ sau một thời gian ngắn, ông nhập ngũ một trung đoàn kỵ binh Áo đóng giữ tại đây vào năm 1778 và tham gia cuộc Chiến tranh Kế vị Bayern với Friedrich Đại đế ở Tiệp Khắc. Sau hai năm phục vụ quân đội Áo, năm 1780, ông chuyển sang quân đội của Thân vương quốc Bayreuth-Ansbach. Đến năm 1782, khi người Anh thuê lính của thân vương xứ Ansbach-Bayreuth và vương hầu khác ở Đức trong Chiến tranh Cách mạng Mỹ, ông đã đầu quân cho Vương triều Anh. Gneisenau được điều vào một trung đoàn Chasseur với cấp hàm Thiếu úy. Mặc dù Neihardt không thu được nhiều kinh nghiệm thực chiến do cuộc chiến trên thực tế đã chấm dứt khi ông đến Halifax (một thành phố cũ ở Canada), thời gian phục vụ tại Bắc Mỹ đã giúp ông trực tiếp học được chiến thuật chiến tranh du kích.[2][4][5] Ông ở lại Canada cho đến khi trở về Ansbach vào cuối năm 1783, và được đổi sang lực lượng bộ binh.

Nhận thấy việc phục vụ quân đội xứ Ansbach-Bayreuth không đem lại nhiều cơ hội thăng tiến, vào năm 1785 ông trực tiếp đệ đơn xin gia nhập quân đội Phổ là Friedrich Đại đế. Sau một buổi yết kiến riêng với nhà vua, Gneisenau được bổ nhiệm vào Bộ Tham mưu Hậu cần Potsdam – tiền thân sơ khai của Bộ Tổng tham mưu với cấp bậc Thiếu úy. Tài nghệ và phong thái đĩnh đạc của viên sĩ quan khôi ngô tuấn tú này đã làm đẹp lòng nhà vua. Sau một thời gian ngắn, ông được đổi vào Trung đoàn Bộ binh nhẹ Chaumontet tại đồn binh Löwenberg (Lwowek) ở Schlesien với cấp bậc Trung úy. Tại đồn binh của mình, ông dành thời gian học tiếng Anh, tiếng Pháp, tiếng Ba Lan và nghiên cứu lịch sử, văn học và khoa học chiến tranh.

Trong vòng 30 năm tới, cho đến khi Gneisenau nghỉ hưu vào năm 1816, ông thăng tiến chậm qua các cấp bậc, phục vụ các đồn quân không mấy ai biết đến ở Schlesien trong suốt gần 20 năm trước khi khẳng định năng lực của mình trong chiến đấu chống những đạo quân Pháp hùng mạnh của Napoléon.[4][5] Được phong chức Stabskapitän (Đại úy tham mưu) vào tháng 6 năm 1790,[2] Gneisenau đảm nhiệm cương vị này tại Schlesien cho đến năm 1792, khi ông và tiểu đoàn của mình tham gia chiến đấu cùng với quân đội Nga tại Ba Lan trong các sự kiện dẫn tới cuộc chia cắt Ba Lan lần thứ ba. Vào năm 1795, ông được thăng cấp Đại úy và lãnh chức Đại đội trưởng ở Jauer (Jawor). Tận dụng khoảng thời gian hòa bình, Gneisenau tranh thủ mở rộng kiến thức của mình các vấn đề nghĩa vụ, bộ binh, kỵ binh, pháo binh, kỹ thuật quân sự, chiến thuật và địa lý quân sự. Vào năm 1796, ông kết hôn với Caroline von Kottwitz.